// https://www.lintcode.com/problem/word-abbreviation/description
// 639. Word Abbreviation
// 给出一组 n 个不同的非空字符串，您需要按以下规则为每个单词生成 最小 的缩写。

// 从第一个字符开始，然后加上中间缩写掉的字符的长度，后跟最后一个字符。
// 如果有冲突，就是多个单词共享相同的缩写，使用较长的前缀，而不是仅使用第一个字符，直到使单词的缩写的映射变为唯一。 换句话说，最终得到的缩写不能映射到多个原始单词。
// 如果缩写不会使单词更短，则不进行缩写，保持原样。
// 样例
// 给出 dict = ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
// 返回 ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
// 注意事项
// n 和每个单词的长度均不会超过 400。
// 每个单词的长度大于 1。
// 这些词只包括小写英文字母。
// 返回答案应该与原始数组保持相同的顺序。



// 思路：
// • 直接模拟
// • 求出abbr，有重复就增加prefix继续求abbr
// • 怎么判断重复？
// – Hash桶计数



// class Solution {
// public:
//     /**
//      * @param dict: an array of n distinct non-empty strings
//      * @return: an array of minimal possible abbreviations for every word
//      */
//     vector<string> wordsAbbreviation(vector<string> &dict) {
//         vector<string> result;
//         map<string, string> result_map;
//         map<string, vector<string>> record_map;
//         for (int i = 0; i < dict.size(); i++)
//         {
//             string word = dict[i];
//             vector<string> record;
//             int len = word.length();
//             for (int i = 1; i < len; i++)
//             {
//                 string mid = len - i - 1 > 0 ? to_string(len - i - 1): ""; 
//                 string abb = word.substr(0, i) + mid + word[len - 1];
//                 if (abb.length() < len || abb == word)
//                 {
//                     record.push_back(abb);
//                 }
//             }
//             record_map[word] = record;
//         }
//         for (string d: dict)
//         {
//             int i = 0;
//             string tmp = record_map[d][i];
//             if (result_map.find(tmp) == result_map.end())
//             {
//                 result_map[tmp] = d;
//             }
//             else
//             {
//                 string conf_word = result_map[tmp];
//                 result_map.erase(tmp);
//                 while (record_map[conf_word][i] == record_map[d][i])
//                 {
//                     i++;
//                 }
//                 result_map[record_map[conf_word][i]] = conf_word; 
//                 result_map[record_map[d][i]] = d;
//                 result.insert(find(result.begin(), result.end(), tmp), record_map[conf_word][i]);
//                 result.erase(find(result.begin(), result.end(), tmp));
//             }
//             result.push_back(record_map[d][i]);
//         }
//         return result;
//     }
// };



struct Node {
    string str;
    int index;
    Node (string s, int i) {
        str = s;
        index = i;
    }
};

struct Compare {
    bool operator() (Node &a, Node &b) {
        
        if (a.str[0] < b.str[0]) {
            return true;
        }
        if (a.str[0] == b.str[0] && a.str.back() < b.str.back()) {
            return true;
        }
        if (a.str[0] == b.str[0] && a.str.back() == b.str.back()) {
            if (a.str.size() < b.str.size()) {
                return true;
            }
            if (a.str.size() == b.str.size()) {
                return a.str < b.str;
            }
        }
        return false;
    }
};

class Solution {
public:
    /**
     * @param dict: an array of n distinct non-empty strings
     * @return: an array of minimal possible abbreviations for every word
     */
    vector<string> wordsAbbreviation(vector<string> &dict) {
        
        vector<string> ans(dict.size(), "");
        vector<Node> todo;
        
        for (int i = 0; i < dict.size(); ++i) {
            if (dict[i].size() <= 3) {
                ans[i] = dict[i];
                continue;
            }
            todo.push_back(Node(dict[i], i));
        }
        
        if (todo.empty()) {
            return ans;
        }
        
        sort(todo.begin(), todo.end(), Compare());
        
        string last = todo[0].str[0] + to_string(todo[0].str.size() - 2) + todo[0].str.back();;
        
        for (int i = 0; i < todo.size() - 1; ++i) {
            string str1 = todo[i].str;
            string str2 = todo[i + 1].str;
            string new1, new2;
            if (str1.size() != str2.size() || str1[0] != str2[0] || str1.back() != str2.back()) {
                new1 = str1[0] + to_string(str1.size() - 2) + str1.back();
                new2 = str2[0] + to_string(str2.size() - 2) + str2.back();
            }
            else {
                int j = 1;
                while (str1[j] == str2[j]) {
                    j++;
                }
                if (j + 4 <= str1.size()) {
                    new1 = str1.substr(0, j + 1) + to_string(str1.size() - j - 2) + str1.back();
                    new2 = str2.substr(0, j + 1) + to_string(str2.size() - j - 2) + str2.back();
                }
                else {
                    new1 = str1;
                    new2 = str2;
                }
            }
            ans[todo[i].index] = (new1.size() > last.size()) ? new1 : last;
            last = new2;
        }
        
        ans[todo.back().index] = last;
        
        return ans;
    }
};